/**
 * 折半插入排序
 * @param {Array} arr - 待排序数组
 * @returns {Array} - 排序后的数组（引用相同）
 */
function BinaryInsertionSort(arr) {
    for (let i=1;i<arr.length;i++){
        //1.初始化
        let current=arr[i]
        let left=0
        let right=i-1
        //2.找到插入位置：当left和right相邻或者相等时，说明找到了正确位置
        while(left<=right){
            let mid=Math.floor((left+right)/2)
            //中间值小于当前值，说明要继续往右边找
            if(arr[mid]<current){
                left=mid+1
            }
            //中间值大于等于当前值，说明要往左边找
            else {
                right=mid-1
            }
        }
        //3.后移元素:只能从后面的元素开始往后移
        //哪些需要移动？目前需要插入的元素前面一个--> i-1;left所在的元素（因为最后一次查找结束时，left=mid+1,指向应该插入的位置
        for(let j=i-1;j>=left;j--){
            arr[j+1]=arr[j]
        }
        //4.插入元素
        arr[left]=current
    }
    return arr;
}

// 测试函数
function testInsertionSort() {
    let arr = [];
    for (let i = 0; i < 10; i++) {
        arr.push(Math.floor(Math.random() * 100));
    }
    
    console.log("排序前:", arr);
    BinaryInsertionSort(arr);
    console.log("排序后:", arr);
    
    // 验证排序结果
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            console.log("排序失败!");
            return;
        }
    }
    console.log("排序成功!");
}

// 运行测试
testInsertionSort();